package com.jxb.four;

import com.jxb.tree.TreeNode;
import com.sun.xml.internal.org.jvnet.mimepull.CleanUpExecutorFactory;

/**
 * 删除二叉搜索树中的节点
 * 思路：
 *  1：若没有右子树，将左子树替换掉当前节点
 *  2：若没有左子树，将右子树替换掉当前节点
 *  3：若都有，将左子树添加到右子树的最左节点，然后将右子树替换为当前节点
 */
public class DeleteNodeInBST_450 {

    public static void main(String[] args) {

    }


    public TreeNode deleteNode(TreeNode root, int key) {
        //目标节点小于当前节点
        if (key < root.val) {
            root.left = deleteNode(root.left,key);
        }
        //目标节点大于当前节点
        else if (key > root.val) {
            root.right = deleteNode(root.right,key);
        }
        //找到了当前节点
        else {
            //若当前节点的左子树为空
            if (root.left == null) {
                return root.right;
            }
            //若当前节点的右子树为空
            else if (root.right == null) {
                return root.left;
            }else {
                TreeNode rightMin = root.right;
                while (rightMin.left != null) {
                    rightMin = rightMin.left;
                }
                rightMin.left = root.left;
                root = root.right;
            }
        }
        return root;
    }

}
